home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / subdivision.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.7 KB  |  50 lines
  1. {\magonebf 6.6 Planar Subdivisions (subdivision)}
  2.  
  3. \decl subdivision I 
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $S$ of the parameterized data type \name\ is a 
  8. subdivision of the two-dimensional plane, i.e., an embedded planar graph 
  9. with straight line edges (see also sections 5.3 and 5.6). With each node 
  10. $v$ of $S$ is associated a point, called the position of $v$ and with each 
  11. face of $S$ is associated an information from data type $I$, called the 
  12. information type of $S$.
  13.  
  14.  
  15. {\bf 2. Creation}
  16.  
  17. \create S (GRAPH\<point,I\>\ G)
  18.  
  19. creates an instance \var\ of type \name\ and initializes it to 
  20. the subdivision represented by the parameterized directed graph $G$. 
  21. The node entries of $G$ (of type point)  define the positions of the 
  22. corresponding nodes of \var. Every face $f$ of \var\ is assigned the 
  23. information of one of its bounding edges in $G$.  \precond $G$ represents 
  24. a planar subdivision, i.e., a straight line embedded planar map.
  25.  
  26.  
  27. \bigskip
  28. {\bf 2. Operations}
  29. \medskip
  30. \+\op point  position {node\ v}       
  31.                                       { returns the position of node $v$.}
  32. \smallskip
  33. \+\op ftype  inf      {face\ f}       
  34.                                       { returns the information of face $f$.}
  35. \smallskip
  36. \+\op face   locate\_point {point\ p} 
  37.                                       { returns the face containing point $p$.}
  38. \smallskip
  39.  
  40.  
  41. \bigskip
  42. {\bf 3. Implementation}
  43.  
  44. Planar subdivisions are implemented by parameterized planar maps and an
  45. additional data structure for point location based on persistent search trees
  46. ([DSST89]). Operations position and inf take constant time, a locate\_point 
  47. operation takes time $O(\log^2 n)$. Here $n$ is the number of nodes. 
  48. The space requiremnt and the initialization time is $O(n^2)$.
  49.  
  50.